0790. 多米诺和托米诺平铺【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 动态规划

1. 📝 题目描述

• leetcode

有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。

给定整数 n，返回可以平铺 2 x n 的面板的方法的数量。返回对 10^9 + 7 取模 的值。

平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。

---

示例 1：

输入: n = 3
输出: 5
解释: 五种不同的方法如上所示。

示例 2：

输入: n = 1
输出: 1

---

提示：

• 1 <= n <= 1000

2. 🎯 s.1 - 动态规划

c

int numTilings(int n) {
    long long MOD = 1000000007;
    if (n <= 2) return n;
    long long dp[n + 1];
    dp[0] = 1; dp[1] = 1; dp[2] = 2; dp[3] = 5;
    for (int i = 4; i <= n; i++) {
        dp[i] = (2 * dp[i - 1] % MOD + dp[i - 3]) % MOD;
    }
    return (int)dp[n];
}

js

/**
 * @param {number} n
 * @return {number}
 */
var numTilings = function (n) {
  const MOD = 1e9 + 7
  if (n <= 2) return n
  const dp = new Array(n + 1).fill(0)
  dp[0] = 1
  dp[1] = 1
  dp[2] = 2
  dp[3] = 5
  for (let i = 4; i <= n; i++) {
    dp[i] = (((2 * dp[i - 1]) % MOD) + dp[i - 3]) % MOD
  }
  return dp[n]
}

py

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 10**9 + 7
        if n <= 2:
            return n
        dp = [0] * (n + 1)
        dp[0], dp[1], dp[2], dp[3] = 1, 1, 2, 5
        for i in range(4, n + 1):
            dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD
        return dp[n]

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

算法思路：

• 状态转移方程：$dp[i]=2\times dp[i-1]+dp[i-3]$
• 包含多米诺骨牌和托米诺骨牌两种形状的平铺组合